package graph;


import java.util.*;

/**
 * @BelongsProject: leetcode
 * @BelongsPackage: graph
 * @author: 肖
 * @date: 2022/1/29 20:58
 * @Description: 拓扑排序
 * @since JDK 11
 */

public class TopologicalSort {
//    核心思想 找到入度为0 结点 删除 更新图 直到图为0
    public  static List<NodeG> TopologicalSort(Graph graph){
//        K-V 某一node-剩余入度
        HashMap<NodeG,Integer> inMap = new HashMap<>();
//        入度为0组成的队列
        Queue<NodeG> zeroInQueue =new LinkedList<>();
        for (NodeG node : graph.nodes.values()){
            inMap.put(node,node.in);
            if(node.in==0){
                zeroInQueue.add(node);
            }
        }
//       拓扑排序的结果依次加入result
        List<NodeG> result = new ArrayList<>();
        while(!zeroInQueue.isEmpty()){
            NodeG cur = zeroInQueue.poll();
            result.add(cur);
            for (NodeG next: cur.nexts){
                inMap.put(next,inMap.get(next)-1);
                if(inMap.get(next)==0){
                    zeroInQueue.add(next);
                }
            }
        }
    return result;
    }

}
